1. Field
The present invention relates to the field of error detection, and more particularly, to error detection methods utilized in a data processing system for identifying errors in stored data.
2. Art Background
The complexity of modern data processing systems requires that some means be employed in order to detect errors in stored, retrieved and otherwise manipulated data bits. For example, errors may be introduced into data as a result of mechanical and/or electrical variations in the data processing system, such as foreign material disposed on the magnetic read-write heads of a tape or disk mass media storage device. Other potential sources which may introduce errors in, or otherwise alter, data bits include the natural wearing of the storage medium, variations in the power supply voltage for the data processing system, as well as "soft" errors induced by radioactive impurities in the housing of the storage device and cosmic rays.
A variety of methods have been developed in order to detect errors introduced into stored or otherwise manipulated data. One common error detection system includes the use of a simple check-sum code. Typically, data is organized in terms of records which comprise a plurality of bytes. Each byte in turn is comprised of a plurality of bits (typically 8). A system employing the use of a simple check-sum method performs an exclusive-OR operation between each sequential byte within the record. Thus, as illustrated in FIG. 1, the 8 bits comprising byte A.sub.1 are exclusive-ORed with the 8 bits comprising A.sub.2. Similarly, the resultant binary quantity of the operation between A.sub.1 and A.sub.2 is exclusive-ORed with the bits comprising byte A.sub.3, and so on. The check-sum is defined as the net resultant binary quantity obtained from these repetitive exclusive-OR operations. The resultant check-sum quantity is typically inserted at the end of the record, as illustrated in FIG. 1 as the A.sub.i.
In many data processing systems, data is written onto a magnetic recording media such as a magnetic disk or tape. In those systems employing the use of a check-sum error detection method, the data in the form of numerous bytes comprising the entire record, is written sequentially onto the magnetic medium such that byte A.sub.1 is written first with subsequent bytes then written, and finally one or more bytes comprising the check-sum resultant is disposed at the end of the record. When retrieving the data from the magnetic medium, the data processing system sequentially reads the content of the entire record while recalculating the value of the check-sum. After the entire record has been read from the recording medium, the recalculated check-sum value is compared with the check-sum previously recorded as part of the record. If the two check-sums do not identically match, an error in the data is assumed.
The use of a simple check-sum error detection method is not as protective as one naturally assumes. For example, the simple check-sum method has inherent pattern sensitivity for short burst errors randomly distributed throughout the record. Thus use of an exclusive-OR operation between sequential bytes within the record renders it possible for errors to cancel one another, and therefore not be detected. For example, if the bit state of bit #2 within a particular byte of the record is altered as a result of a mechanical and/or electrical malfunction (e.g. a 1 is shifted to a 0 bit state), and bit #2 of another byte is similarly altered (a 0 bit state is inadvertently shifted to a 1 bit state), the errors in the bytes will cancel during the exclusive-OR operation. In the case of two random bits in error, the probability of an error misdetection is approximately one out of eight.
One method for improving the error detection rate for the simple check-sum is to add "interleaving". For example, a 3 byte check-sum generates three separate resultant check-sum values for a record. As illustrated in FIG. 2, the first check-sum value may be determined for bytes A.sub.1, A.sub.2, A.sub.3, etc. which represent sequential check-sum interleaved bytes. Similarly, a second checksum would be calculated for the bytes B.sub.1, B.sub.2, B.sub.3, etc., and a third for bytes C.sub.1, C.sub.2, C.sub.3, etc. Although interleaving significantly lowers the misdetection probability for long random error bursts, the misdetection probability for sparse error bursts has been found to be unacceptably high.
Accordingly, there exists a need to provide a means to increase the detectability of errors in stored and manipulated data. As will be disclosed, the present invention provides apparatus and methods for improving error detectability by randomizing and propagating an error throughout the data record. The randomization and propagation of an error significantly increases the probability of its detection.